#include <stdio.h>
#include <stdlib.h>
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int *nextGreaterElement(int *nums1, int nums1Size, int *nums2, int nums2Size, int *returnSize) {
    //单调栈
    int stackDat[nums2Size];
    int stackTop = 0;
    int hashSet[100001] = {0};    //表示在num1中是否出现过
    for (int i = 0; i < nums1Size; i++) {
        hashSet[nums1[i]] = i + 1;
    }
    *returnSize = nums1Size;
    int *returnNums = (int *) malloc(sizeof(int) * nums1Size);
//    for (int i = 0; i < nums2Size; i++) {
//        //单调递减队列
//        while (stackTop && (nums2[i] > stackDat[stackTop - 1])) {
//            int hashIndex = hashSet[stackDat[stackTop - 1]];
//            if (hashIndex != 0) {
//                returnNums[hashIndex - 1] = nums2[i];
//            }
//            stackTop--;
//        }
//        stackDat[stackTop++] = nums2[i];
//    }
    for (int i = 0; i < nums2Size; ++i) {
        while (stackTop && (nums2[i] > stackDat[stackTop - 1])) {
            int hashIndex = hashSet[stackDat[stackTop - 1]];
            if (hashIndex != 0) {
                returnNums[hashIndex - 1] = nums2[i];
            }
            stackTop--;
        }
        stackDat[stackTop++] = nums2[i];
    }
    while (stackTop > 0) {
        int hashIndex = hashSet[stackDat[stackTop - 1]];
        if (hashIndex != 0) {
            returnNums[hashIndex - 1] = -1;
        }
        stackTop--;
    }
    // [5,2,6,9,11,3,7]
//    for (int i = 0; i < 10001; ++i) {
//        printf("i == %d, value = %d\n", i, hashSet[i]);
//    }
    return returnNums;
}

int main() {
    // nums1 = [4,1,2], nums2 = [1,3,4,2].
//    int test1[3] = {4, 1, 2};
//    int test2[4] = {1, 3, 4, 2};
    int test1[7] =  {3,1,5,7,9,2,6};
    int test2[8] = {1,2,3,5,6,7,9,11};
    int retSize = 0;
    int *ret = nextGreaterElement(test1, 7, test2, 8, &retSize);
    printf(" start");
}